1. Field
The present application is directed to methods and apparatus for encoding and decoding data for the purpose of detecting and/or correcting errors in binary data, e.g., through the use of parity check codes, such as low density parity check (LDPC) codes.
2. Background
Error correcting codes are ubiquitous in communications and data storage systems. Recently, considerable interest has grown in a class of codes known as low-density parity-check (LDPC) codes.
LDPC codes are often represented by bipartite graphs, called Tanner graphs, in which one set of nodes, the variable nodes, correspond to bits of a codeword and the other set of nodes, the constraint nodes, sometimes called check nodes, correspond to a set of parity-check constraints which define the code. Edges in the graph connect variable nodes to constraint nodes. A variable node and a constraint node are said to be neighbors if they are connected by an edge in the graph. For simplicity, it is generally assumed that a pair of nodes is connected by at most one edge.
A bit sequence associated one-to-one with the variable nodes is a codeword of the code if and only if, for each constraint node, the bits neighboring the constraint (via their association with variable nodes) sum to zero modulo two, i.e., they comprise an even number of ones.
In some cases a codeword may be punctured. This refers to the act of removing or puncturing certain bits from the codeword and not actually transmitting them. When encoding an LDPC code, however, bits which are to be punctured are still determined. Thus, puncturing has little or no impact on the encoding process. For this reason, the possibility of puncturing will not be considered in the remainder of this application.
The decoders and decoding algorithms used to decode LDPC codewords operate by exchanging messages within the graph along the edges and updating these messages by performing computations at the nodes based on the incoming messages. Such algorithms are generally referred to as message passing algorithms. Each variable node in the graph is initially provided with a soft bit, termed a received value that indicates an estimate of the associated bit's value as determined by observations from, e.g., the communications channel. The encoding process also operates in part along the edges of the graph but the connection is less precise.
The number of edges attached to a node, i.e., a variable node or constraint node, is referred to as the degree of the node. A regular graph or code is one for which all variable nodes have the same degree, j, and all constraint nodes have the same degree, k. In this case, the code is a (j,k) regular code. These codes were originally invented by Gallager (1961). In contrast to a “regular” code, an irregular code has constraint nodes and/or variable nodes of differing degrees. For example, some variable nodes may be of degree 4, others of degree 3 and still others of degree 2.
While irregular codes can be more complicated to represent and/or implement, it has been shown that irregular LDPC codes can provide superior error correction/detection performance when compared to regular LDPC codes.
While encoding efficiency and high data rates are important for an encoding and/or decoding system to be practical for use in a wide range of devices, e.g., consumer devices, it is important that the encoders and/or decoders be capable of being implemented at reasonable cost. Accordingly, there is a need to efficiently implement encoding/decoding schemes used for error correction and/or detection purposes, e.g., in terms of hardware costs.